home *** CD-ROM | disk | FTP | other *** search
/ Programming Languages Suite / ProgramD2.iso / Borland / Borland C++ V5.02 / CHESS.PAK / MOVGEN.CPP < prev    next >
C/C++ Source or Header  |  1997-05-06  |  15KB  |  519 lines
  1. //----------------------------------------------------------------------------
  2. // ObjectWindows - (C) Copyright 1991, 1993 by Borland International
  3. //----------------------------------------------------------------------------
  4. #include <owl/pch.h>
  5. #include <owl/defs.h>
  6. #include <math.h>
  7. //#include "wcdefs.h"
  8. #include "externs.h"
  9.  
  10. //
  11. //  Globals
  12. //
  13. static ATTACKTABTYPE attack[240];
  14. ATTACKTABTYPE *AttackTab = &attack[120];
  15. SETOFPIECE BitTab[7] = {0, 1, 2, 4, 8, 0x10, 0x20};
  16. int DirTab[8] = { 1, -1, 0x10, -0x10, 0x11, -0x11, 0x0f, -0x0f};
  17. int KnightDir[8] = {0x0E, -0x0E, 0x12, -0x12, 0x1f, -0x1f, 0x21, -0x21};
  18. int PawnDir[2] = {0x10, -0x10};
  19. MOVETYPE Next;
  20. int BufCount, BufPnt;
  21. MOVETYPE Buffer[81];
  22. CASTMOVETYPE  CastMove[2][2] = { {{2, 4}, {6, 4}}, {{0x72, 0x74}, {0x76, 0x74}} };
  23.  
  24.  
  25. void
  26. CalcAttackTab()
  27. {
  28.   for (int sq = -0x77; sq <= 0x77; sq++) {
  29.     AttackTab[sq].pieceset = 0;
  30.     AttackTab[sq].direction = 0;
  31.   }
  32.  
  33.   for (DIRTYPE dir = 7; dir >= 0; dir--) {
  34.     for (unsigned char i = 1; i < 8; i++) {
  35.       if (dir < 4)
  36.         AttackTab[DirTab[dir]*i].pieceset = SETOFPIECE(BitTab[queen]+BitTab[rook]);
  37.       else
  38.         AttackTab[DirTab[dir]*i].pieceset = SETOFPIECE(BitTab[queen]+BitTab[bishop]);
  39.       AttackTab[DirTab[dir]*i].direction = DirTab[dir];
  40.     }
  41.     AttackTab[DirTab[dir]].pieceset += SETOFPIECE(BitTab[king]);
  42.     AttackTab[KnightDir[dir]].pieceset = SETOFPIECE(BitTab[knight]);
  43.     AttackTab[KnightDir[dir]].direction = KnightDir[dir];
  44.   }
  45. }
  46.  
  47. //
  48. //  calculate whether apiece placed on asquare attacks the square
  49. //
  50. short
  51. PieceAttacks(PIECETYPE apiece, COLORTYPE acolor, SQUARETYPE asquare, SQUARETYPE square)
  52. {
  53.   int x = square - asquare;
  54.   if (apiece == pawn)  //  pawn attacks
  55.     return abs(x - PawnDir[acolor]) == 1;
  56.  
  57.   //  other attacks: can the piece move to the square?
  58.   if (AttackTab[x].pieceset & BitTab[apiece]) {
  59.     if (apiece == king || apiece == knight)
  60.       return 1;
  61.  
  62.     //  are there any blocking pieces in between?
  63.     EDGESQUARETYPE sq = asquare;
  64.     do {
  65.       sq += AttackTab[x].direction;
  66.     } while (sq != square && Board[sq].piece == empty);
  67.     return sq == square;
  68.   }
  69.   return 0;
  70. }
  71.  
  72. //
  73. //  calculate whether acolor attacks the square with at pawn
  74. //
  75. short
  76. PawnAttacks(COLORTYPE acolor, SQUARETYPE square)
  77. {
  78.   EDGESQUARETYPE sq = square - PawnDir[acolor] - 1;  //  left square
  79.   if (!(sq & 0x88))
  80.     if (Board[sq].piece == pawn && Board[sq].color == acolor)
  81.       return 1;
  82.  
  83.   sq += 2;  //  right square
  84.   if (!(sq & 0x88))
  85.     if (Board[sq].piece == pawn && Board[sq].color == acolor)
  86.       return 1;
  87.  
  88.   return 0;
  89. }
  90.  
  91. //
  92. //  Calculates whether acolor attacks the square
  93. //
  94. short
  95. Attacks(COLORTYPE acolor, SQUARETYPE square)
  96. {
  97.   if (PawnAttacks(acolor, square))  //  pawn attacks
  98.     return 1;
  99.  
  100.   //  Other attacks:  try all pieces, starting with the smallest
  101.   for (INDEXTYPE i = OfficerNo[acolor]; i >= 0; i--)
  102.     if (PieceTab[acolor][i].ipiece != empty)
  103.       if (PieceAttacks(PieceTab[acolor][i].ipiece, acolor,
  104.           PieceTab[acolor][i].isquare, square))
  105.         return 1;
  106.   return 0;
  107. }
  108.  
  109. //
  110. //  check whether inpiece is placed on square and has never moved
  111. //
  112. short
  113. Check(SQUARETYPE square, PIECETYPE inpiece, COLORTYPE incolor)
  114. {
  115.   if(Board[square].piece == inpiece && Board[square].color == incolor) {
  116.     DEPTHTYPE dep = DEPTHTYPE(Depth - 1);
  117.     while (MovTab[dep].movpiece != empty) {
  118.       if (MovTab[dep].new1 == square)
  119.         return 0;
  120.       dep--;
  121.     }
  122.     return 1;
  123.   }
  124.   return 0;
  125. }
  126.  
  127. //
  128. //  Calculate whether incolor can castle
  129. //
  130. void
  131. CalcCastling(COLORTYPE incolor,  CASTDIRTYPE *cast)
  132. {
  133.   SQUARETYPE square = 0;
  134.  
  135.   if (incolor == black)
  136.     square = 0x70;
  137.   *cast = zero;
  138.   if (Check(square + 4, king, incolor)) { //  check king
  139.     if (Check(square, rook, incolor))
  140.       ((int)*cast) += lng;                //  check a-rook
  141.     if (Check(square + 7, rook, incolor))
  142.       ((int)*cast) += shrt;               //  check h-rook
  143.   }
  144. }
  145.  
  146. //
  147. //  check if move is a pawn move or a capture
  148. //
  149. inline short
  150. RepeatMove(MOVETYPE* move)
  151. {
  152.   return move->movpiece != empty && move->movpiece != pawn &&
  153.          move->content == empty && !move->spe;
  154. }
  155.  
  156. //----------------------------------------------------------------------------
  157.  
  158. //
  159. //  Count the number of moves since last capture or pawn move
  160. //  The game is a draw when fiftymovecnt = 100
  161. //
  162. FIFTYTYPE
  163. FiftyMoveCnt()
  164. {
  165.   FIFTYTYPE cnt = 0;
  166.   while (RepeatMove(&MovTab[Depth - cnt]))
  167.     cnt++;
  168.   return cnt;
  169. }
  170.  
  171. //
  172. //  Calculate how many times the position has occured before
  173. //  The game is a draw when repetition = 3;
  174. //  movetab[back..Depth] contains the previous moves
  175. //  When immediate is set, only immediate repetion is checked
  176. //
  177. REPEATTYPE
  178. Repetition(short immediate)
  179. {
  180.   DEPTHTYPE lastdep, compdep, tracedep, checkdep, samedepth;
  181.   SQUARETYPE tracesq, checksq;
  182.   REPEATTYPE repeatcount;
  183.  
  184.   repeatcount = 1;
  185.   lastdep = samedepth = DEPTHTYPE(Depth + 1);  //  current postion
  186.   compdep = DEPTHTYPE(samedepth - 4);      //  First position to compare
  187.  
  188.   //  MovTab[lastdep..Depth] contains previous relevant moves
  189.   while (RepeatMove(&MovTab[lastdep - 1]) && (compdep < lastdep || !immediate))
  190.     lastdep--;
  191.   if (compdep < lastdep)
  192.     return repeatcount;
  193.   checkdep = samedepth;
  194.   for (;;) {
  195.     checkdep--;
  196.     checksq = MovTab[checkdep].new1;
  197.     for (tracedep = DEPTHTYPE(checkdep + 2); tracedep < samedepth; tracedep += DEPTHTYPE(2))
  198.       if (MovTab[tracedep].old == checksq)
  199.         goto TEN;
  200.  
  201.     //  Trace the move backward to see if it has been 'undone' earlier
  202.     tracedep = checkdep;
  203.     tracesq = MovTab[tracedep].old;
  204.     do {
  205.       if (tracedep-2 < lastdep)
  206.         return repeatcount;
  207.       tracedep -= (DEPTHTYPE)2;
  208.       //  Check if piece has been moved before
  209.       if (tracesq == MovTab[tracedep].new1)
  210.         tracesq = MovTab[tracedep].old;
  211.     } while (tracesq != checksq || tracedep > compdep + 1);
  212.     if (tracedep < compdep) {  //  Adjust evt. compdep
  213.       compdep = tracedep;
  214.       if ((samedepth - compdep) % 2 == 1) {
  215.         if (compdep == lastdep) return repeatcount;
  216.         compdep --;
  217.       }
  218.       checkdep = samedepth;
  219.     }
  220.     //  All moves between SAMEDEP and compdep have been checked,
  221.     //  so a repetition is found
  222. TEN:
  223.     if (checkdep <= compdep) {
  224.       repeatcount++;
  225.       if (compdep - 2 < lastdep) return repeatcount;
  226.       checkdep = samedepth = compdep;
  227.       compdep -= (DEPTHTYPE)2;
  228.     }
  229.   }
  230. }
  231.  
  232. //
  233. //  Test whether a move is possible
  234. //
  235. //  On entry:
  236. //   Move contains a full description of a move, which
  237. //   has been legally generated in a different position.
  238. //   MovTab[Depth - 1] contains last performed move.
  239. //
  240. //  On exit:
  241. //   KillMovGen indicates whether the move is possible
  242. //
  243. short
  244. KillMovGen(MOVETYPE* move)
  245. {
  246.   SQUARETYPE castsq;
  247.   PIECETYPE promote;
  248.   CASTDIRTYPE castdir;
  249.   CASTTYPE cast;
  250.   short killmov;
  251.  
  252.   killmov = 0;
  253.   if (move->spe && move->movpiece == king) {
  254.     CalcCastling(Player, &cast);   //  Castling
  255.     if (move->new1 > move->old)
  256.       castdir = shrt;
  257.     else
  258.       castdir = lng;
  259.  
  260.     if (cast & castdir) {  //  Has king or rook moved before
  261.       castsq = (int)((move->new1 + move->old) / 2);
  262.       //  Are the squares empty ?
  263.       if  (Board[move->new1].piece == empty)
  264.         if (Board[castsq].piece == empty)
  265.           if (move->new1 > move->old || Board[move->new1-1].piece == empty)
  266.             //  Are the squares unattacked
  267.             if (!Attacks(Opponent, move->old))
  268.               if (!Attacks(Opponent, move->new1))
  269.                 if (!Attacks(Opponent, castsq))
  270.                   killmov = 1;
  271.     }
  272.  
  273.   } else {
  274.     if (move->spe && move->movpiece == pawn) {
  275.       //  E.p. capture
  276.       //  Was the Opponent's move a 2 square move?
  277.       if (MovTab[Depth-1].movpiece == pawn)
  278.         if (abs(MovTab[Depth-1].new1 - MovTab[Depth-1].old) >= 0x20)
  279.           if (Board[move->old].piece == pawn && Board[move->old].color == Player)
  280.             killmov = move->new1 == (MovTab[Depth-1].new1+MovTab[Depth-1].old) / 2;
  281.     } else {
  282.       if (move->spe) {            // Normal test
  283.         promote = move->movpiece; // Pawn promotion
  284.         move->movpiece = pawn;
  285.       }
  286.  
  287.       //  Is the content of Old and New1 squares correct?
  288.       if (Board[move->old].piece == move->movpiece)
  289.         if (Board[move->old].color == Player)
  290.           if (Board[move->new1].piece == move->content)
  291.             if (move->content == empty || Board[move->new1].color == Opponent) {
  292.               if (move->movpiece == pawn) {  //  Is the move possible?
  293.                 if (abs(move->new1 - move->old) < 0x20)
  294.                   killmov = 1;
  295.                 else
  296.                   killmov = Board[(move->new1+move->old) / 2].piece == empty;
  297.               } else
  298.                 killmov = PieceAttacks(move->movpiece, Player,
  299.               move->old, move->new1);
  300.             }
  301.       if (move->spe)
  302.         move->movpiece = promote;
  303.     }
  304.   }
  305.   return killmov;
  306. }
  307.  
  308. //
  309. //  Store a move in buffer
  310. //
  311. static void
  312. Generate()
  313. {
  314.   BufCount++;
  315.   Buffer[BufCount] = Next;
  316. }
  317.  
  318. //
  319. //  Generates pawn promotion
  320. //
  321. static void
  322. PawnPromotionGen()
  323. {
  324.   Next.spe = 1;
  325.   for (PIECETYPE promote = queen; promote <= knight; ((int)promote)++) {
  326.     Next.movpiece = promote;
  327.     Generate();
  328.   }
  329.   Next.spe = 0;
  330. }
  331.  
  332. //
  333. //  Generates captures of the piece on new1 using PieceTab
  334. //
  335. static void
  336. CapMovGen()
  337. {
  338.   Next.spe = 0;
  339.   Next.content = Board[Next.new1].piece;
  340.   Next.movpiece = pawn;
  341.   EDGESQUARETYPE nextsq = Next.new1 - PawnDir[Player];
  342.   for (EDGESQUARETYPE sq = nextsq-1; sq <= nextsq+1; sq++)
  343.     if (sq != nextsq)
  344.       if ((sq & 0x88) == 0)
  345.         if (Board[sq].piece == pawn && Board[sq].color == Player) {
  346.           Next.old = sq;
  347.           if (Next.new1 < 8 || Next.new1 >= 0x70)
  348.             PawnPromotionGen();
  349.           else
  350.             Generate();
  351.         }
  352.  
  353.   //  Other captures, starting with the smallest pieces
  354.   for (INDEXTYPE i = OfficerNo[Player]; i >= 0; i--)
  355.     if (PieceTab[Player][i].ipiece != empty && PieceTab[Player][i].ipiece != pawn)
  356.       if (PieceAttacks(PieceTab[Player][i].ipiece, Player,
  357.           PieceTab[Player][i].isquare, Next.new1)) {
  358.         Next.old = PieceTab[Player][i].isquare;
  359.         Next.movpiece = PieceTab[Player][i].ipiece;
  360.         Generate();
  361.       }
  362. }
  363.  
  364. //
  365. //  generates non captures for the piece on old
  366. //
  367. static void
  368. NonCapMovGen()
  369. {
  370.   DIRTYPE  first, last, dir;
  371.   int direction;
  372.   EDGESQUARETYPE  newsq;
  373.  
  374.   Next.spe = 0;
  375.   Next.movpiece = Board[Next.old].piece;
  376.   Next.content = empty;
  377.   switch (Next.movpiece) {
  378.     case king:
  379.       for (dir = 7; dir >= 0; dir--) {
  380.         newsq = Next.old + DirTab[dir];
  381.         if (!(newsq & 0x88))
  382.         if (Board[newsq].piece == empty) {
  383.           Next.new1 = newsq;
  384.           Generate();
  385.         }
  386.       }
  387.       break;
  388.  
  389.     case knight:
  390.       for (dir = 7; dir >= 0; dir--) {
  391.         newsq = Next.old + KnightDir[dir];
  392.         if (!(newsq & 0x88))
  393.         if (Board[newsq].piece == empty) {
  394.           Next.new1 = newsq;
  395.           Generate();
  396.         }
  397.       }
  398.       break;
  399.  
  400.     case queen:
  401.     case rook:
  402.     case bishop:
  403.       first = 7;
  404.       last = 0;
  405.       if (Next.movpiece == rook)
  406.         first = 3;
  407.       if (Next.movpiece == bishop)
  408.         last = 4;
  409.       for (dir = first; dir >= last; dir--) {
  410.         direction = DirTab[dir];
  411.         newsq = Next.old + direction;
  412.         //  Generate all non captures in the direction
  413.         while (!(newsq & 0x88)) {
  414.           if (Board[newsq].piece != empty) goto TEN;
  415.           Next.new1 = newsq;
  416.           Generate();
  417.           newsq = Next.new1 + direction;
  418.         }
  419. TEN:    continue;
  420.       }
  421.       break;
  422.  
  423.     case pawn:
  424.       Next.new1 = Next.old + PawnDir[Player];  //  one square forward
  425.       if (Board[Next.new1].piece == empty) {
  426.         if (Next.new1 < 8 || Next.new1 >= 0x70)
  427.           PawnPromotionGen();
  428.         else {
  429.           Generate();
  430.           if (Next.old < 0x18 || Next.old >= 0x60) {
  431.             Next.new1 += (Next.new1 - Next.old); // 2 squares forward
  432.             if (Board[Next.new1].piece == empty)
  433.               Generate();
  434.           }
  435.         }
  436.       }
  437.   }
  438. }
  439.  
  440. //
  441. //  The move generator.
  442. //  InitMovGen generates all possible moves and places them in a buffer.
  443. //  Movgen will the generate the moves one by one and place them in next.
  444. //
  445. //  On entry:
  446. //   Player contains the color to move.
  447. //   MovTab[Depth-1] the las performed move.
  448. //
  449. //  On exit:
  450. //   Buffer contains the generated moves.
  451. //
  452. //  The moves are generated in the order:
  453. //   Captures
  454. //   Castlings
  455. //   Non captures
  456. //   E.p. captures
  457. //
  458.  
  459. void
  460. InitMovGen()
  461. {
  462.   CASTDIRTYPE castdir;
  463.   EDGESQUARETYPE sq;
  464.   INDEXTYPE index;
  465.  
  466.   BufCount = BufPnt = 0;
  467.   //  generate all captures starting with captures of
  468.   //  largest pieces
  469.   for (index = 1; index <= PawnNo[Opponent]; index++)
  470.     if (PieceTab[Opponent][index].ipiece != empty) {
  471.       Next.new1 = PieceTab[Opponent][index].isquare;
  472.       CapMovGen();
  473.     }
  474.  
  475.   Next.spe = 1;
  476.   Next.movpiece = king;
  477.   Next.content = empty;
  478.   for (castdir = CASTDIRTYPE(lng-1); castdir <= shrt-1; ((int)castdir)++) {
  479.     Next.new1 = CastMove[Player][castdir].castnew;
  480.     Next.old = CastMove[Player][castdir].castold;
  481.     if (KillMovGen(&Next)) Generate();
  482.   }
  483.  
  484.   //  generate non captures, starting with pawns
  485.   for (index = PawnNo[Player]; index >= 0; index--)
  486.     if (PieceTab[Player][index].ipiece != empty) {
  487.       Next.old = PieceTab[Player][index].isquare;
  488.       NonCapMovGen();
  489.     }
  490.   if (MovTab[Depth-1].movpiece == pawn)  //  E.p. captures
  491.     if (abs(MovTab[Depth-1].new1 - MovTab[Depth-1].old) >= 0x20) {
  492.       Next.spe = 1;
  493.       Next.movpiece = pawn;
  494.       Next.content = empty;
  495.       Next.new1 = (MovTab[Depth-1].new1 + MovTab[Depth-1].old) / 2;
  496.       for (sq = MovTab[Depth-1].new1-1; sq <= MovTab[Depth-1].new1+1;
  497.               sq++)
  498.         if (sq != MovTab[Depth-1].new1)
  499.           if (!(sq & 0x88)) {
  500.             Next.old = sq;
  501.             if (KillMovGen(&Next)) Generate();
  502.           }
  503.     }
  504. }
  505.  
  506. //
  507. //  place next move from the buffer in next.  Generate zeromove when there
  508. //  are no more moves.
  509. //
  510. void MovGen()
  511. {
  512.   if (BufPnt >= BufCount)
  513.     Next = ZeroMove;
  514.   else {
  515.     BufPnt++;
  516.     Next = Buffer[BufPnt];
  517.   }
  518. }
  519.